package com.suanfa;


/**
 * 插值查找
 *
 * @Author weijingchen
 * @Date 2025/5/27 22:18
 * @Version 1.0.0
 */
public class Test06 {
    // 主函数测试
    public static void main(String[] args) {
        int[] sortedArray = {10, 22, 35, 40, 45, 50, 80, 82, 85, 90, 100};
        int target = 82;

        int index = interpolationSearch(sortedArray, target);
        if (index != -1) {
            System.out.println("目标值 " + target + " 在数组中的索引为: " + index);
        } else {
            System.out.println("未找到目标值 " + target);
        }
    }

    // 插值查找方法
    public static int interpolationSearch(int[] arr, int target) {
        int low = 0;
        int high = arr.length - 1;

        while (low <= high && arr[low] <= target && arr[high] >= target) {
            // 防止除以0的情况
            if (arr[low] == arr[high]) {
                if (arr[low] == target) {
                    return low;
                } else {
                    return -1;
                }
            }

            // 插值计算位置
            int pos = low + ((target - arr[low]) * (high - low)) / (arr[high] - arr[low]);

            if (arr[pos] == target) {
                return pos;
            } else if (arr[pos] < target) {
                low = pos + 1;
            } else {
                high = pos - 1;
            }
        }

        return -1; // 未找到
    }


}
